/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._02_01;

import java.util.HashMap;

/**
 * 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
 *
 * 示例1:
 *
 *  输入：[1, 2, 3, 3, 2, 1]
 *  输出：[1, 2, 3]
 * 示例2:
 *
 *  输入：[1, 1, 1, 1, 2]
 *  输出：[1, 2]
 * 提示：
 *
 * 链表长度在[0, 20000]范围内。
 * 链表元素在[0, 20000]范围内。
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._02_01
 * @ClassName: RemoveDuplicateNodes
 * @Author: linyaonan
 * @Date: 2020/3/25 18:06
 */
public class RemoveDuplicateNodes {

    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) {
            return null;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode p = pre;
        ListNode h = head;
        while (h != null) {
            int val = h.val;
            if (map.containsKey(val)) {
                p.next = h.next;
            } else {
                map.put(val, 1);
                p = h;
            }
            h = h.next;
        }
        return pre.next;
    }

}
